package 将有序数组转换为二叉搜索树;

/**
 * @author: AirMan
 * @date: 2025/4/9 11:26
 * @description: 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 递归
        // 递归的参数：nums，left,right
        // 递归的返回值：TreeNode 当前的子树
        // 递归的终止条件：low < hight
        // 单层递归逻辑：left,right的中间数构造为为根节点，中间数的left构造为其左子树，right构造为右子树，子树内容根据数组切割即可
        // 左闭右闭 [left,right]
        return buildAVL(nums,0, nums.length-1);
    }

    public TreeNode buildAVL(int[] nums, int left, int right) {

        if (left > right) {
            return null;
        }
        // left,right的中间数构造为为根节点
        int index = (left + right) / 2;
        TreeNode root = new TreeNode(nums[index]);
        // 构造左子树
        root.left = buildAVL(nums, left, index - 1);
        // 构造右子树
        root.right = buildAVL(nums, index + 1, right);
        return root;
    }
}
